In computing, a task is a unit of work. A process or thread is said to “execute” a task if the process or thread performs the unit of work or causes the unit of work to be performed. Because a program may require millions of tasks to be executed, efficiently scheduling the tasks becomes extremely important. If tasks are not scheduled efficiently, then the program may take a significant time to execute.
One approach for implementing a task scheduling system is to provide calls to put a certain task to sleep and wake it up again. Tasks may be multiplexed over worker threads, with each worker thread executing tasks from a ready queue. If a task becomes blocked by, for example, issuing an I/O operation, then the task is “put to sleep” by placing the task in a wait queue, which may be one of many wait queues, each for a different type of I/O operation. Once the I/O operation completes, the task is woken up using the wake operation. “Waking” a task involves dequeuing the task from the wait queue and enqueuing the task in a ready queue so work for the task will be resumed once the task reaches the front of the ready queue.
Under this approach, the ready queue becomes a shared resource between the task executing thread and the thread handling callbacks generated upon completion of I/O operations. Because multiple threads access the ready queue and the wait queue, synchronization constructs are added to each queue operation, which results in adding overhead to task operations. Such overhead may not be significant if the overhead is small relative to latency of the I/O operations.
The approaches described in this section are approaches that could be pursued, but not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section.